//There are N children standing in a line. Each child is assigned a rating value
//. 
//
// You are giving candies to these children subjected to the following requireme
//nts: 
//
// 
// Each child must have at least one candy. 
// Children with a higher rating get more candies than their neighbors. 
// 
//
// What is the minimum candies you must give? 
//
// Example 1: 
//
// 
//Input: [1,0,2]
//Output: 5
//Explanation: You can allocate to the first, second and third child with 2, 1, 
//2 candies respectively.
// 
//
// Example 2: 
//
// 
//Input: [1,2,2]
//Output: 4
//Explanation: You can allocate to the first, second and third child with 1, 2, 
//1 candies respectively.
//             The third child gets 1 candy because it satisfies the above two c
//onditions.
// 
// Related Topics 贪心算法


//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    fun candy(ratings: IntArray): Int {
        val candies = IntArray(ratings.size)
        for (i in ratings.indices) {
            candies[i] = 1
            fixCandy(i, ratings, candies)
        }
        return candies.sum()
    }

    fun fixCandy(i: Int, ratings: IntArray, candies: IntArray) {
        if (i <= 0) {
            return
        }
        if (ratings[i] > ratings[i - 1]) {
            candies[i] = Math.max(candies[i - 1] + 1, candies[i])
        } else if (ratings[i] < ratings[i - 1]) {
            if (candies[i] <= candies[i - 1]) {
                candies[i - 1] = candies[i] + 1
                fixCandy(i - 1, ratings, candies)
            }
        }
    }
}
//leetcode submit region end(Prohibit modification and deletion)
